The Fast Fourier Transform (FFT) is the generic name for a class of computationally efficient algorithms that implement the Discrete Fourier Transform (DFT). Until the advent of integrated circuit (IC) devices, the FFT could not be computed fast enough to be of use in the field of digital signal processing. Even now, faster and better FFT IC devices are still being pursued by many.
In order to further increase the speed of such devices, the manner in which certain basic computational blocks are implemented is scrutinized. One such computational block is the complex multiplier. In the FFT algorithm, there are numerous multiplication operations involving multiplying complex numbers which effectively quadruple the number of multiplications. Accordingly, it is desirable to investigate methods which provide a faster multiplication computation.
Additionally, in order to achieve the greatest speed improvement in such FFT devices, the computations are preferably performed in parallel without many iterations through the same computational blocks in the duration of many clock cycles. Such parallelism requires using enough computational blocks so that a result may be obtained in one clock cycle. Therefore, it is further desirable to pack the multiplier hardware to a size that allows all hardware to reside within the physical space of an integrated circuit device.